#include <iostream>
#include <queue>

using namespace  std;

/*
It is a google phone interview question:
Given a graph and a start node, duplicate the graph that is can be
traversed from start node.

Solution:
In this solution, we use the dfs to traverse from start node, and
use visit[] to track whether the node has been duplicated. In this 
example, the graph is represented as open linked list. Please try
yourself for matrix case.
*/

typedef struct _Node
{
	int NodeIndex;
	int Weight;
	struct _Node* Next;
} Node;

/*
Print the graph, it is auxilary routine
*/
void PrintGraph( Node **Graph, int NodeNumber)
{
	if( !Graph || NodeNumber < 1 )
		return;
	for( int i= 0; i<NodeNumber; i++ )
	{
		Node* head = Graph[i];
		while( head )
		{
			cout<<"Node "<<i<<" to Node "<<head->NodeIndex<<" length "<<head->Weight<<endl;
			head = head->Next;
		}
	}
}

// Create the empty graph, it is auxilary routine
Node** CreateGraph(int n)
{
	if( n < 1)
		return NULL;

	Node **Graph = new Node* [n];

	for(int i=0; i<n; i++ )
	{
		Graph[i] = NULL;
	}
	return Graph;
}

// Delete a graph, it is auxilary routine
void DeleteGraph( Node **Graph, int NodeNumber)
{
	for( int i=0; i<NodeNumber; i++ )
	{
		Node *head = Graph[i];
		while(head)
		{
			Node *cur = head;
			head = head->Next;
			delete cur;
		}
	}

	delete [] Graph;
}

// Add a new edge to the graph, it is auxilary routine
void AddEdge( Node** Graph, int NodeNumber, int start, int end, int weight)
{
	if( !Graph || start == end || start>=NodeNumber || start<0 || end>=NodeNumber || end<0 )
		return;
	if( Graph[start] )
	{
		// Verify whether there is duplicate
		Node * head = Graph[start];
		while( head)
		{
			if( head->NodeIndex == end )
				return;
			head = head->Next;
		}
	}

	Node * newNode = new Node;
	newNode->NodeIndex = end;
	newNode->Weight = weight;
	newNode->Next = Graph[start];
	Graph[start] = newNode;
}

/*
Duplicate the graph that can be traversed from start node. Using BFS
*/
Node** Duplicate( Node **Graph, int NodeNumber, int start )
{
	if( !Graph || NodeNumber < 1 )
		return NULL;

	// visit is used to track whether the node has been duplicated
	// thus avoid the endless loop
	bool *visit = new bool [NodeNumber];
	for( int i=0; i<NodeNumber; i++ )
	{
		visit[i] = false;
	}

	Node **Clone = CreateGraph(NodeNumber);
	queue<int> Q;

	Q.push(start);
	while( !Q.empty() )
	{
		int curIndex = Q.front();
		Node *cur = Graph[curIndex];
		Q.pop();
		if( visit[curIndex] )
			continue;
		visit[curIndex] = true;

		while(cur)
		{
			Node* newNode = new Node;
			newNode->NodeIndex = cur->NodeIndex;
			newNode->Weight = cur->Weight;
			newNode->Next = Clone[curIndex];
			Clone[curIndex] = newNode;

			Q.push(cur->NodeIndex);
			cur = cur->Next;
		}
	}

    delete[] visit;
	return Clone;
}

#define NODE_NUMBER		7
int main()
{
	Node **Graph = CreateGraph(NODE_NUMBER);
	if( !Graph )
		return -1;

	AddEdge( Graph, NODE_NUMBER, 0, 1, 2);
	AddEdge( Graph, NODE_NUMBER, 0, 2, 4);
	AddEdge( Graph, NODE_NUMBER, 2, 3, 2);
	AddEdge( Graph, NODE_NUMBER, 3, 4, 2);
	AddEdge( Graph, NODE_NUMBER, 4, 0, 2);
	AddEdge( Graph, NODE_NUMBER, 4, 1, 2);
	AddEdge( Graph, NODE_NUMBER, 5, 6, 2);
	PrintGraph(Graph, NODE_NUMBER);
	cout<<endl;

	Node **clone = Duplicate( Graph, NODE_NUMBER, 0 );
	PrintGraph(clone, NODE_NUMBER);

	// delete the two graphs here
	DeleteGraph( Graph, NODE_NUMBER );
	DeleteGraph( clone, NODE_NUMBER );

	cout<<"Press any key to terminate..."<<endl;
	return getchar();
}
